package 中等.贪心思想;

import java.util.Arrays;

/**
 * 给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，
 * 每艘船可以承载的最大重量为 limit。
 * 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
 * 返回 承载所有人所需的最小船数 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/boats-to-save-people
 */
public class 救生艇_881 {

    public static void main(String[] args) {

    }


    /**
     * 贪心思路
     * 1，如果体重最轻的人和最重的人不能同时乘一条船，
     * 那么最重的人和任何人都不能乘同一条船
     * 2，如果体重最轻的人和最重的人可以同时乘一条船，
     * 为了使船能够承载更多的重量，两个人一条船
     *
     * @param people
     * @param limit
     * @return
     */
    public int numRescueBoats(int[] people, int limit) {
        int ans = 0;
        Arrays.sort(people);
        int left = 0, right = people.length - 1;
        while (left < right) {
            if (people[left] + people[right] <= limit) {
                left++;
                right--;
            } else {
                right--;
            }
            ans++;
        }
        return left == right ? ans + 1 : ans;
    }

}
